from __future__ import with_statement

class TabuSearch(object):
    pass
    
#    def evaluate_solution(partitions, graph):
#        connections = {}
#        for v in graph:
#            connections[v] = [len(graph[v].intersection(partitions[0])), 
#                              len(graph[v].intersection(partitions[1]))]
#        z = sum(connections[v][1] for v in partitions[0])
#        assert z == sum(connections[v][0] for v in partitions[1])
#        return z, connections
#        
#    def find_move(target, partitions, graph, connections, tabu, tabulen, iteration):
#        mindelta = INF
#        candidates = []
#        for v in partitions[1 - target]:
#            if random() > float(tabu[v] - iteration) / tabulen:
#                delta = connections[v][1 - target] - connections[v][target]
#                if delta < mindelta:
#                    mindelta = delta
#                    candidates = [v]
#                elif delta == mindelta:
#                    candidates.append(v)
#        if len(candidates) > 0:
#            return choice(candidates), mindelta
#        tabu = dict((v, 0) for v in graph)
#        return find_move(target, partitions, graph, connections, tabu, tabulen, iteration)
#        
#    def move(target, partitions, graph, connections, tabu, tabulen, iteration):
#        vertex, delta = find_move(target, partitions, graph, connections, tabu, tabulen, iteration)
#        partitions[1 - target].remove(vertex)
#        partitions[target].add(vertex)
#        tabu[vertex] = iteration + tabulen
#        for v in graph[vertex]:
#            connections[v][target] += 1
#            connections[v][1 - target] -= 1
#        return delta
#        
#    def tabu_search(partitions, graph, tabulen, 
#                    max_iter=INF, max_cpu=INF, 
#                    log=True, verbosity=5, seed=None):
#        assert len(graph) % 2 == 0
#        log = Logger(enabled=log, verbosity=verbosity)
#        clock = Clock()
#        rng_seed(seed)
#        
#        cost, connections = evaluate_solution(partitions, graph)
#        tabu = dict((v, 0) for v in graph)
#        bestcost = cost
#        bestsol = (set(partitions[0]), set(partitions[1]))
#        iteration = 0
#        log("Initial solution:\n\t%s\n\t%s" % partitions, level=2)
#        log("STARTING COST: %d" % (bestcost,), level=5)
#        try:
#            while iteration < max_iter and clock.total() < max_cpu:
#                with clock.tracking():
#                    log("Tabu Search, iteration %d (%s)" % (iteration, clock.total()))
#                    cost += move(0, partitions, graph, connections, tabu, tabulen, iteration)
#                    log("Intermediate solution:\n\t%s\n\t%s" % partitions)
#                    cost += move(1, partitions, graph, connections, tabu, tabulen, iteration)
#                    log("Complete solution:\n\t%s\n\t%s" % partitions)
#                    if cost < bestcost:
#                        log("IMPROVEMENT: %d -> %d" % (bestcost, cost), level=5)
#                        log("   NEW BEST:\n\t%s\n\t%s" % partitions, level=2)
#                        bestcost = cost
#                        bestsol = (set(partitions[0]), set(partitions[1]))
#                    iteration += 1
#        except KeyboardInterrupt:
#            pass
#        log("   ELAPSED CPU TIME: %s" % (clock.total(),), level=2)
#        log("BEST SOLUTION FOUND: %d\n\t%s\n\t%s" % (bestcost, bestsol[0], bestsol[1]), level=2)
#        return bestcost, bestsol
#        
#
#    # --------------------------------------------
#    def start(self):
#        
#    def moves(self, solution):
#        raise NotImplementedError()
#        
#    def accept(self, sol_x, sol_y):
#        raise NotImplementedError()
#        
#    def apply(self, solution, move):
#        raise NotImplementedError()
#        
#    def objective(self, solution):
#        raise NotImplementedError()
#        
